public class demo1 {
    class Solution {
        public int minCut(String s) {
            int n=s.length();
            boolean[][]ret=new boolean[n][n];
            for(int i=n-1;i>=0;i--){
                for(int j=i;j<n;j++){
                    if(s.charAt(i)==s.charAt(j)){
                        ret[i][j]=i+1<j?ret[i+1][j-1]:true;
                    }
                }
            }
            int[]dp=new int[n];
            for(int i=0;i<n;i++)dp[i]=Integer.MAX_VALUE;
            for(int i=0;i<n;i++){
                for(int j=i;j<n;j++){
                    if(ret[0][i])dp[i]=0;
                    else{
                        if(ret[i][j]){
                            dp[i]=Math.min(dp[j-1]+1,dp[i]);
                        }
                    }
                }
            }
            return dp[n-1];
        }
    }
}
